1799E - City Union - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
char s[N][N];
int n, m;
bool a[N], b[N];
bool used[N][N];
const int DX[] = {-1, 1, 0, 0};
const int DY[] = {0, 0, -1, 1};
int LX, RX, LY, RY;

bool checkCell(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    return s[x][y] == '#';
}

void dfs(int x, int y) {
    LX = min(LX, x);
    RX = max(RX, x);
    LY = min(LY, y);
    RY = max(RY, y);
    used[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + DX[i], yy = y + DY[i];
        if (!checkCell(xx, yy)) continue;
        if (used[xx][yy]) continue;
        dfs(xx, yy);
    }
}

vector<array<int, 4>> findComps() {
    for (int x = 0; x < n; x++)
        for (int y = 0; y < m; y++)
            used[x][y] = 0;
    vector<array<int, 4>> res;
    for (int x = 0; x < n; x++)
        for (int y = 0; y < m; y++)
            if (s[x][y] == '#' && !used[x][y]) {
                LX = LY = N;
                RX = RY = -1;
                dfs(x, y);
                res.push_back({LX, RX, LY, RY});
            }
    return res;
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", s[i]);
    while (true) {
        bool fnd = false;
        for (int i = 0; i < n; i++) {
            int l = m, r = -1;
            for (int j = 0; j < m; j++)
                if (s[i][j] == '#') {
                    if (r == -1) l = j;
                    r = j;
                }
            if (r == -1) continue;
            for (int j = l; j < r; j++)
                if (s[i][j] == '.') {
                    fnd = true;
                    s[i][j] = '#';
                }
        }
        for (int j = 0; j < m; j++) {
            int l = n, r = -1;
            for (int i = 0; i < n; i++)
                if (s[i][j] == '#') {
                    if (r == -1) l = i;
                    r = i;
                }
            if (r == -1) continue;
            for (int i = l; i < r; i++)
                if (s[i][j] == '.') {
                    fnd = true;
                    s[i][j] = '#';
                }
        }
        if (!fnd) break;
    }
    auto C = findComps();

    if ((int)C.size() == 1) {
        for (int i = 0; i < n; i++)
            printf("%s\n", s[i]);
        printf("\n");
        return;
    }
    assert((int)C.size() == 2);

    if (C[0][0] > C[1][0]) swap(C[0], C[1]);

    int lx1 = C[0][0];
    int rx1 = C[0][1] + 1;
    int ly1 = C[0][2];
    int ry1 = C[0][3] + 1;

    int lx2 = C[1][0];
    int rx2 = C[1][1] + 1;
    int ly2 = C[1][2];
    int ry2 = C[1][3] + 1;

    assert(lx1 < rx1 && rx1 <= lx2 && lx2 < rx2);

    if (ly1 < ly2) {
        assert(ly1 < ry1 && ry1 <= ly2 && ly2 < ry2);
        int x = lx1;
        while (s[x][ry1 - 1] == '.') x++;
        int y = ry2 - 1;
        while (s[lx2][y] == '.') y--;
        for (int i = x; i <= lx2; i++)
            s[i][ry1 - 1] = '#';
        for (int j = ry1 - 1; j <= y; j++)
            s[lx2][j] = '#';
    } else {
        swap(ly1, ly2);
        swap(ry1, ry2);
        assert(ly1 < ry1 && ry1 <= ly2 && ly2 < ry2);
        int x = rx2 - 1;
        while (s[x][ry1 - 1] == '.') x--;
        int y = ry2 - 1;
        while (s[rx1 - 1][y] == '.') y--;
        for (int i = rx1 - 1; i <= x; i++)
            s[i][ry1 - 1] = '#';
        for (int j = ry1 - 1; j <= y; j++)
            s[rx1 - 1][j] = '#';
    }

    while (true) {
        bool fnd = false;
        for (int i = 0; i < n; i++) {
            int l = m, r = -1;
            for (int j = 0; j < m; j++)
                if (s[i][j] == '#') {
                    if (r == -1) l = j;
                    r = j;
                }
            if (r == -1) continue;
            for (int j = l; j < r; j++)
                if (s[i][j] == '.') {
                    fnd = true;
                    s[i][j] = '#';
                }
        }
        for (int j = 0; j < m; j++) {
            int l = n, r = -1;
            for (int i = 0; i < n; i++)
                if (s[i][j] == '#') {
                    if (r == -1) l = i;
                    r = i;
                }
            if (r == -1) continue;
            for (int i = l; i < r; i++)
                if (s[i][j] == '.') {
                    fnd = true;
                    s[i][j] = '#';
                }
        }
        if (!fnd) break;
    }

    for (int i = 0; i < n; i++)
        printf("%s\n", s[i]);
    printf("\n");
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solve();
}